package puzzle.projecteuler.p200;

import java.util.ArrayList;
import java.util.List;



public class Problem199C {

	private static List<Double> circles = new ArrayList<Double>();	//save all circles
	
	/**
	 * 参考 http://mathworld.wolfram.com/SoddyCircles.html
	 *  
	 * answer	: 0.003960869448011772
	 * time cost: 158ms 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();

		//initialize
		double r = 2*Math.sqrt(3) - 3;
		circles.add(-1.0);
		circles.add(r);
		circles.add(r);
		circles.add(r);
		Arc3[] list = new Arc3[] {
			new Arc3(0, 1, 2),
			new Arc3(0, 2, 3),
			new Arc3(0, 3, 1),
			new Arc3(1, 2, 3)
		};
		
		//iterate
		for (int i = 0; i < 10; i ++) {
			list = iterate(list);
		}
		
		//get result
		double a = 0.0f;
		for (Double d : circles) {
			a += d*d;
		}
		double left = 2.0-a;
		System.out.println(left);
		

		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	private static class Arc3 {
		
		public int c1;
		public int c2;
		public int c3;
		
		public Arc3(int c1, int c2, int c3) {
			this.c1 = c1;
			this.c2 = c2;
			this.c3 = c3;
		}
		
		public double r4() {
			
			double r1 = circles.get(c1);
			double r2 = circles.get(c2);
			double r3 = circles.get(c3);
			
			double x = r1*r2 + r2*r3 + r3*r1;
			double y = 2.0*Math.sqrt(r1*r2*r3*(r1+r2+r3));
			if (Math.abs(x+y) < Math.abs(x-y)) {
				return r1*r2*r3/(x-y);
			} else {
				return r1*r2*r3/(x+y);
			}
		}

		public String toString() {
			return String.format("ARC3: %d, %d, %d", c1, c2, c3);
		}
	}

	private static Arc3[] iterate(Arc3[] current) {
		
		Arc3[] r = new Arc3[current.length*3];
		for (int i = 0; i < current.length; i ++) {
			Arc3 c3 = current[i];
			double r4 = c3.r4();
			int index = circles.size();
			circles.add(r4);
			r[3*i]   = new Arc3(c3.c1, c3.c2, index);
			r[3*i+1] = new Arc3(c3.c2, c3.c3, index);
			r[3*i+2] = new Arc3(c3.c3, c3.c1, index);
		}
		return r;
	}
}